#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <time.h>

#define LL long long

using namespace std;

LL U[5] = {314882150829468584, 427197303358170108,
           102292690726729920, 1698479428772363217, 2006101093849356424};

const LL mod = 2009731336725594113;

int n, q;
int l, r;

LL f(LL x)
{
    return (x % mod) % 2019;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    LL s = 0;
    int t = 0;
    int a[n + 10];
    for (int i = 1; i <= n; i++)
    {
        a[i] = i;
    }
    for (int i = 0; i < q; i++)
    {
        cin >> l >> r;
        for (int j = l; j <= r; j++)
        {
            LL temp = f(a[j]);
            s += temp;
            a[j] = a[j] * U[s % 5] ;
        }
         cout << s << endl;
    }
    
}